/*
 * @Author: wuqingchun
 * @Date: 2024-05-26 10:35:19
 * @Description: 无锁栈实现
 * @LastEditors: wuqingchun
 * @LastEditTime: 2024-05-28 15:54:37
 */

#include <vector>
#include <thread>
#include <iostream>
#include <mutex>
#include <atomic>

template <typename T>
class CasStack
{
    struct StackItem
    {
        T          tData;
        StackItem* pstNext = nullptr;

        StackItem(const T& refData):
            tData(refData)
        {

        }
    };
public:
    CasStack(/* args */)
    {

    }

    ~CasStack()
    {
        Clear();
    }

    bool CasPushV2(const T& refData)
    {
        StackItem* pstItem = new (std::nothrow) StackItem(refData);
        if (pstItem == nullptr)
        {
            return false;
        }

        int i = 0;
        do
        {
            i++;
            pstItem->pstNext = m_atmTop.load();
        } while (!m_atmTop.compare_exchange_strong(pstItem->pstNext, pstItem));

        if (i > 2)
        {
            //printf("===%lu, %d\n", pthread_self(), i);
            std::cout << "[CasPushV2] threadid: " << std::this_thread::get_id() << ", times: " << i << std::endl;
        }

        return true;
    }

    bool CasPopV2(T& refData)
    {
        StackItem* pstCurTop = m_atmTop.load();
        int i = 0;

        while (pstCurTop != nullptr && !m_atmTop.compare_exchange_strong(pstCurTop, pstCurTop->pstNext))
        {
            i++;
            pstCurTop = m_atmTop.load();
        }

        if (i > 2)
        {
            //printf("===%lu, %d\n", pthread_self(), i);
            std::cout << "[CasPopV2] threadid: " << std::this_thread::get_id() << ", times: " << i << std::endl;
        }

        if (pstCurTop == nullptr)
        {
            return false;
        }
        
        refData = pstCurTop->tData;
        delete pstCurTop;

        return true;
    }

    bool CasPush(const T& refData)
    {
        StackItem* pstItem = new (std::nothrow) StackItem(refData);
        if (pstItem == nullptr)
        {
            return false;
        }

        int i = 0;
        StackItem* pstCurTop = nullptr;
        do
        {
            pstCurTop = m_pstTop;
            pstItem->pstNext = pstCurTop;
            i++;
        } while (!__sync_bool_compare_and_swap(&m_pstTop, pstCurTop, pstItem));

        if (i > 2)
        {
            //printf("===%lu, %d\n", pthread_self(), i);
            std::cout << "[CasPush] threadid: " << std::this_thread::get_id() << ", times: " << i << std::endl;
        }

        return true;
    }

    bool CasPop(T& refData)
    {
        StackItem* pstCurTop = m_pstTop;
        int i = 0;

        while (pstCurTop != nullptr && !__sync_bool_compare_and_swap(&m_pstTop, pstCurTop, pstCurTop->pstNext))
        {
            i++;
            pstCurTop = m_pstTop;
        }

        if (i > 2)
        {
            //printf("===%lu, %d\n", pthread_self(), i);
            std::cout << "[CasPop] threadid: " << std::this_thread::get_id() << ", times: " << i << std::endl;
        }

        if (pstCurTop == nullptr)
        {
            return false;
        }
        
        refData = pstCurTop->tData;
        delete pstCurTop;

        return true;
    }
    
    bool Push(const T& refData)
    {
        StackItem* pstItem = new (std::nothrow) StackItem(refData);
        if (pstItem == nullptr)
        {
            return false;
        }

        if (m_pstTop != nullptr)
        {
            pstItem->pstNext = m_pstTop;
        }

        m_pstTop = pstItem;

        return true;
    }

    bool Pop(T& refData)
    {
        if (m_pstTop == nullptr)
        {
            return false;
        }

        StackItem* pstTop = m_pstTop;
        m_pstTop = m_pstTop->pstNext;

        refData = pstTop->tData;
        delete pstTop;

        return true;
    }

    bool SafePush(const T& refData)
    {
        StackItem* pstItem = new (std::nothrow) StackItem(refData);
        if (pstItem == nullptr)
        {
            return false;
        }

        std::lock_guard<std::mutex> objLG(m_objMtx);
        if (m_pstTop != nullptr)
        {
            pstItem->pstNext = m_pstTop;
        }

        m_pstTop = pstItem;

        return true;
    }

    bool SafePop(T& refData)
    {
        std::lock_guard<std::mutex> objLG(m_objMtx);

        if (m_pstTop == nullptr)
        {
            return false;
        }

        StackItem* pstTop = m_pstTop;
        m_pstTop = m_pstTop->pstNext;

        refData = pstTop->tData;
        delete pstTop;

        return true;
    }

    void Clear()
    {
        StackItem* pstItem = m_pstTop;
        StackItem* pstNext = nullptr;

        while (pstItem != nullptr)
        {
            pstNext = pstItem->pstNext;
            delete pstItem;
            pstItem = pstNext;
        }

        m_pstTop = nullptr;
    }
private:
    StackItem* m_pstTop {nullptr};
    std::mutex m_objMtx;
    std::atomic<StackItem*> m_atmTop {};
};

int main(int argc, char** argv)
{
    CasStack<int> objStack;
    std::vector<std::thread> vecThreads;

    if (argc < 2)
    {
        std::cout << "Usage: " << argv[0] << " thread-number" << std::endl;
        return 0;
    }
    
    for (int i = 0; i < atoi(argv[1]); i++)
    {
        vecThreads.push_back(std::thread([&]()
        {
            for (int i = 0; i < 1000; i++)
            {
                if (!objStack.CasPush(i))
                {
                    std::cout << "i: " << i << std::endl;
                }
            }

            for (int i = 0; i < 1000; i++)
            {
                int iData;
                if (!objStack.CasPop(iData))
                {
                    std::cout << "iData: " << iData << std::endl;
                }
            }
        }));
    }

    for (auto& refThread : vecThreads)
    {
        refThread.join();
    }

    return 0;
}